package linkedlist;

import javax.sound.midi.Soundbank;
import java.util.LinkedList;
import java.util.Stack;
import java.util.UnknownFormatConversionException;

/**
 * @author huangxin
 * @date 2019/6/20-9:47
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");

        //创建列表
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addByOrder(hero1);
        linkedList.addByOrder(hero2);
        linkedList.addByOrder(hero3);
        linkedList.addByOrder(hero4);

        linkedList.list();

        //获取倒数第2个节点
        HeroNode eleByIndex = findLastIndexNode(linkedList.getHead(), 2);
        System.out.println("倒数第二个");
        System.out.println(eleByIndex);

        //倒叙打印
        System.out.println("逆序打印,没有改变链表结构");
        reversePrint(linkedList.getHead());


//        System.out.println("有效节点个数为:" + getLength(linkedList.getHead()));
//
//        //遍历
//        linkedList.list();
//
//        //修改节点
//        HeroNode newHeroNode = new HeroNode(2, "小卢", "麒麟");
//        linkedList.update(newHeroNode);
//        linkedList.list();
//
//        //删除节点
//        linkedList.delete(1);
//        linkedList.delete(2);
//        linkedList.delete(2);
//        System.out.println("有效节点个数为:" + getLength(linkedList.getHead()));
//        linkedList.list();

//        System.out.println("反转后");
//        reverse(linkedList.getHead());

        HeroNode hero5 = new HeroNode(2, "林冲", "豹子头");
        HeroNode hero6 = new HeroNode(6, "宋江", "及时雨");
        HeroNode hero7 = new HeroNode(7, "吴用", "智多星");
        HeroNode hero8 = new HeroNode(8, "卢俊义", "玉麒麟");
        SingleLinkedList linkedList2 = new SingleLinkedList();
        linkedList2.addByOrder(hero5);
        linkedList2.addByOrder(hero6);
        linkedList2.addByOrder(hero7);
        linkedList2.addByOrder(hero8);


        System.out.println("合并后");
        HeroNode merge = merge(linkedList.getHead(), linkedList2.getHead());
        print(merge);
    }


    /**
     * 合并两个单链表
     */
    public static HeroNode merge(HeroNode head1, HeroNode head2) {
        //判断是否有链表为空
        if (head1.next == null) {
            return head2;
        } else if (head2.next == null) {
            return head1;
        }
        //新建一个head
        HeroNode newHead = new HeroNode(0, "", "");
        //新链表的临时节点
        HeroNode temp = newHead;
        //两个临时节点
        HeroNode node1 = head1.next;
        HeroNode node2 = head2.next;
        while (true) {
            if (node1 == null) {
                //如果遍历完其中一个,则结束循环,把另一个存储在新链表的尾部
                temp.next = node2;
                break;
            } else if (node2 == null) {
                temp.next = node1;
                break;
            }
            //如果节点一小于节点二
            if (node1.no < node2.no) {
                //节点一排在前面
                temp.next = node1;
                //后移
                node1 = node1.next;
                //后移
                temp = temp.next;
            } else if (node1.no > node2.no) {//同上
                temp.next = node2;
                node2 = node2.next;
                temp = temp.next;
            } else if (node1.no == node2.no) {//如果节点一样,共存
                //存储第一个
                temp.next = node1;
                //后移
                node1 = node1.next;
                //存储第二个
                temp.next.next = node2;
                //后移
                node2 = node2.next;
                //后移两位
                temp = temp.next.next;
            }
        }
        return newHead;
    }


    /**
     * 逆序打印单向列表(使用栈方式)
     */
    public static void reversePrint(HeroNode head) {
        //如果链表为空
        if (head.next == null) {
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode current = head.next;
        while (current != null) {
            //压栈
            stack.push(current);
            //后移
            current = current.next;
        }
        //出栈打印
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }


    /**
     * 单链表的反转【腾讯面试题，有点难度】
     */
    public static void reverse(HeroNode head) {
        //如果链表为空或者只有一个元素
        if (head.next == null || head.next.next == null) {
            return;
        }
        //获取第一个元素
        HeroNode current = head.next;
        //用于记录下一个元素
        HeroNode next = null;
        //临时的头节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        //如果子节点不为空
        while (current != null) {
            //暂时保存下一个节点
            next = current.next;
            //将cur的下一个节点指向新链表的第一个元素
            current.next = reverseHead.next;
            //将新链表的第一个元素指向cur
            reverseHead.next = current;
            current = next;//后移
        }

        head.next = reverseHead.next;
    }


    /**
     * 查找单链表中的倒数第k个结点
     *
     * @param index
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        //链表为空
        if (head.next == null) {
            return null;
        }

        //获取长度
        int length = getLength(head);

        //第二次遍历 length-index 位置(0起点),就是我们倒数的第K个节点
        if (index <= 0 || index > length) {
            return null;//坐标越界
        }

        //for循环定位到倒数的index
        HeroNode temp = head;
        for (int i = 0; i <= length - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 求单链表中有效节点的个数(不统计头节点)
     *
     * @param heroNode 头节点
     * @return 有效节点的个数
     */
    public static int getLength(HeroNode heroNode) {
        if (heroNode.next == null) {
            //空链表
            return 0;
        }
        HeroNode temp = heroNode.next;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;//遍历
        }
        return count;
    }

    public static void print(HeroNode head) {
        //如果链表为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //头节点不能动
        HeroNode temp = head.next;
        while (true) {
            //判断是否到最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //temp后移
            temp = temp.next;
        }


    }
}

//单向列表
class SingleLinkedList {
    public HeroNode getHead() {
        return head;
    }

    //初始化头节点,头节点不能动,不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    //添加节点到单向列表
    //不考虑编号顺序时
    //1.找到当前链表的最后节点
    //2.将最后节点的next 指向新节点
    public void add(HeroNode heroNode) {
        //head节点不能动
        HeroNode temp = head;
        //遍历链表,找到最后
        while (true) {
            //找到链表的最后节点
            if (temp.next == null) {
                temp.next = heroNode;
                break;
            }
//            if (heroNode.no == temp.no||heroNode.no<=0){
//                System.out.println("元素已存在或编号小于等于0");
//                return;
//            }
//            if (heroNode.no>temp.no&&heroNode.no<temp.next.no){
//                temp.next = heroNode;
//                heroNode.next = temp.next;
//                break;
//            }


            //temp.next不为空,继续循环找下一个节点
            temp = temp.next;
        }
        //当退出循环时,temp就指向了链表的最后
    }

    //排序插入
    public void addByOrder(HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            //说明temp已经在链表的最后
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > heroNode.no) { //位置找到,就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) {
                flag = true;
                break;
            }
            //后移
            temp = temp.next;
        }
        //判断是否要添加
        if (flag) {
            //编号存在,不能添加
            System.out.printf("准备插入的元素编号%d已经存在,不能加入\n", heroNode.no);
        } else {
            //插入到链表中
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    public void update(HeroNode heroNode) {
        if (heroNode.no == 0) {
            System.out.println("不能修改根节点");
            return;
        }
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        boolean flag = false; //表示是否找到该节点
        //找到需要修改的节点,根据编号
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.no == heroNode.no) {
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
            System.out.println("更新成功");
        } else {
            System.out.printf("没有找到编号:%d 的节点,不能修改\n", heroNode.no);
        }
    }


    public void delete(int no) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            //找到需要删除的节点的前一个节点
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
            System.out.println("删除成功");
        } else {
            System.out.printf("没有找到编号:%d 的节点,不能删除\n", no);
        }
    }


    //遍历链表
    public void list() {
        //如果链表为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //头节点不能动
        HeroNode temp = head.next;
        while (true) {
            //判断是否到最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //temp后移
            temp = temp.next;
        }


    }
}

class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next; // 下一个节点


    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
